How do you implement a Min Stack (tracking minimum in O(1))?

Min Stack

javascript

1
Push: O(1).
2
Pop: O(1).
3
Peek: O(1).
4
GetMin: O(1).
5
Auxiliary space: O(n).
6
An alternative stores only values that establish new minimums, reducing typical auxiliary storage.

Difficulty: 5/10

Topics: stack, auxiliary data structures, constant-time min

0-2 years experience

1
We need a stack that can return the current minimum in O(1). How would you implement push, pop, top, and getMin?
2
If you push the values 5, 2, 8, 1 onto your min stack, what does getMin return after each operation?

2-5 years experience

1
Our product uses a min stack to track the lowest price in a sliding window of user actions. If we now need a 'removeBottom' operation that removes the element at the bottom of the stack, how does that affect your design?
2
During a recent bug, getMin started returning the wrong value after a series of pops. Walk me through how you'd debug the issue.
3
What trade‑offs would you consider between using a separate auxiliary stack versus storing (value, currentMin) pairs in the main stack?

5-8 years experience

1
We are building a high‑throughput trading engine where each thread maintains its own min stack for price ticks. How would you ensure thread safety and minimal contention while preserving O(1) getMin?
2
If the stack must be persisted to disk for crash recovery, how would you modify the min‑stack design to allow efficient recovery of the current minimum?

8+ years experience

1
Our legacy system uses a linked‑list based stack with O(N) min retrieval. We want to migrate to a min stack across multiple microservices that share state via a distributed cache. What architectural considerations and migration steps would you propose?
2
When scaling the min‑stack service to handle billions of operations per day, what monitoring, sharding, or alternative data‑structure strategies would you evaluate to keep latency low and guarantee correctness?

❓What is the overall space complexity of your approach?
❓How would you handle integer overflow or extreme value ranges?
❓Can you identify any edge cases that could cause getMin to return an incorrect result?